package com.wfm.leetcode.editor.cn;

import com.wfm.common.ArrayUtils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;

public class PFive1N皇后{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] grid = new char[n][n];
        for (int i = 0; i < grid.length; i++) {
            Arrays.fill(grid[i],'.');
        }
        for (int i = 0; i < n; i++) {
            dfs(grid,0,i);
        }
        return res;
    }
    void dfs(char[][] grid,int i,int j){
        if(!isValid(grid,i,j)){
            return;
        }
        grid[i][j] = 'Q';
        if(i==grid.length-1){
            List<String> path = new ArrayList<>();
            for (char[] c:grid){
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < c.length; k++) {
                    sb.append(c[k]);
                }
                path.add(sb.toString());
            }
            res.add(path);
        }
        for (int k = 0; k < grid[0].length; k++) {
            dfs(grid,i+1,k);
        }
        grid[i][j]='.';
    }
    public boolean isValid(char[][] grid,int i,int j){
        int n = grid[0].length;
        for (int k = i-1; k >=0 ; k--) {
            if(grid[k][j]=='Q') return false;
        }
        for (int k = i-1,l=j-1; k >=0&&l>=0 ; k--,l--) {
            if(grid[k][l]=='Q') return false;

        }
        for (int k = i-1,l=j+1; k >=0&&l<n ; k--,l++) {
            if(grid[k][l]=='Q') return false;

        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFive1N皇后().new Solution();
        List<List<String>> lists = solution.solveNQueens(4);
        System.out.println(lists);
//        char[][] g = new char[][]{
//                {'.','Q','.','.'},
//                {'.','.','.','Q'},
//                {'.','.','.','.'},
//                {'.','.','.','.'}
//        };
//        boolean valid = solution.isValid(g, 2, 0);
//        System.out.println(valid);
    }

}